package com.xiaoyu.binaryTree;

/**
 * @program: DS_and_A
 * @description: 二叉树的最大路径和
 * 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。
 * 同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 *
 * 路径和 是路径中各节点值的总和。
 *
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 *
 * @author: YuWenYi
 * @create: 2021-06-07 09:32
 **/
/*
错误解法
public int maxPathSum1(TreeNode root) {
        dfs(root);
        return max;
    }

    public int dfs1(TreeNode root){
        if (root == null) return 0;
        int leftSum = dfs(root.left);
        int rightSum = dfs(root.right);
        max = Math.max(root.val + leftSum + rightSum, max);
        return  Math.max(root.left == null ? 0 : root.left.val,
                root.right == null ? 0 : root.right.val);
    }*/
public class MaxPathSum_124 {

    private int max = Integer.MIN_VALUE;  //必须是这个,不然路径值如果非常小,那么就影响结果了
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    public int dfs(TreeNode root){
        if (root == null){
            return 0;
        }
        //避免结点值为负数,即如果结点值为负数,就舍弃这个结点,你求和加一个负数还不如不加!
        int leftSum = Math.max(0, dfs(root.left));
        int rightSum = Math.max(0, dfs(root.right));
        max = Math.max(root.val + leftSum + rightSum, max);
        return Math.max(leftSum, rightSum) + root.val;   //这里+root.val是精髓!!
    }


    public static void main(String[] args) {
        TreeNode node = new TreeNode(4,new TreeNode(5),new TreeNode(6));
        TreeNode right = new TreeNode(-3);
        TreeNode left = new TreeNode(2,null,null);
        TreeNode root = new TreeNode(1,left,right);

        MaxPathSum_124 maxPathSum_124 = new MaxPathSum_124();
        System.out.println(maxPathSum_124.maxPathSum(root));

    }
}
